package suanfa;
//给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
//以任意顺序返回这两个数字均可。
//示例 1：
//输入：[1]
//输出：[2,3]
//示例 2：
//输入：[2,3]
//输出：[1,4]
public class missingTwo {
    public int[] missingTwo(int[] nums) {
        //先把所有的数异或在一起
        int tmp=0;
        for(int x:nums) tmp ^=x;
        for(int i=1;i<=nums.length+2;i++) tmp ^=i;
        //2.找出a,b两个数比特位不同的那一位
        int diff=0;
        while(true){
            if(((tmp >>diff) & 1)==1) break;
            else diff++;
        }
        //3.将所有的数按照diff位不同，分为两类异或
        //所有出现两次的数会在同一组中出现两次，相互抵消，最终的结果为a,b
        int[] ret=new int[2];
        for(int x:nums)
            if(((x >>diff) & 1)==1) ret[1] ^=x;
            else ret[0] ^=x;
        for(int i=1;i<=nums.length+2;i++)
            if(((i >>diff) & 1)==1) ret[1] ^=i;
            else ret[0] ^=i;
        return ret;
    }
}
